package aishua.com.mytestapplist.datastructure;

import android.util.Log;

import java.util.LinkedList;

import aishua.com.mytestapplist.utils.LogUtils;

/**
 * Created by aishua on 2018/4/23.
 * 线性表 的链表存储结构
 */

public class MyLink<T> {
    private static final String TAG = "MyLink-";

    private class Node {


        private T data;
        private Node next = null;

        public Node() {

            data = null;
        }

        public Node(T t) {

            this.data = data;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    ", next=" + next +
                    '}';
        }
    }

    private Node head; //保存头结点
    private Node rear; //保存尾结点
    private Node point; //临时结点
    private int length; //结点个数

    //链表数据结构，创建无数据的头结点
    public MyLink() {
        head = new Node();
        rear = head;
        length = 0;
    }

    public MyLink(T t){

        head = new Node(t);
        rear = head;
        length = 0;

    }

    /*
    * 尾插法
    * */
    public void addRear(T t) {

        point = new Node(t);
        rear.next = point;
        rear = point;
        length++;
    }

    //头插法
    public void addHead(T t) {

        point = new Node(t);
        point.next = head;
        head = point;
        if (rear == null) {

            rear = head;
        }
        length++;
    }

    public int length() {

        return length;
    }

    public T getItem(int index) {

        return getNodeByIndex(index).data;
    }

   public Node getNodeByIndex(int i){

       //        容错处理
       if (i < 0 || i > length -1) {

           throw new IndexOutOfBoundsException("索引超出下表范围");
       }
         Node cur = head;
         for (int j =0; j < i && cur !=null; j++,cur =cur.next){

             if (j ==i){

                 return  cur;
             }
         }

         return null;
   }
//按值查找所在位置
   public int locate(T element){

       Node current = head;
       for (int i=0;i< length &&current.next !=null;i ++,current =current.next){
              if (current.equals(element)){

                  return  i;
              }
       }

       return  -1;
   }

//   指定位置插入元素
    public void insert(int i , T t){

       if (i <0 || i>length -1){

           throw new IndexOutOfBoundsException("索引超出下表范围");
       }
       if (head ==null){

           addRear(t);
       }else if(0 ==i){
           addHead(t);
       }else {

           point = new Node(t);
           Node prevNode =getNodeByIndex(i -1);
           point.next = prevNode.next;
           prevNode.next =  point;
       }
        length++;
    }

//    删除指定下标元素,执行成功则返回删除元素
    public T delete(int i){

        if (i <0 || i>length -1){

            throw new IndexOutOfBoundsException("索引超出下表范围");
        }
        if (i ==0){

            head.next = head;
        }
        Node prveNode = getNodeByIndex(i-1);
        prveNode.next= prveNode.next.next;

        return prveNode.data;
    }

    public void clear(){

        head=null;
        rear =null;
        length =0;
    }



}
